`
https://leetcode.cn/problems/count-number-of-ways-to-place-houses/
`

/**
 * @param {number} n
 * @return {number}
 */
var countHousePlacements = function (n) {
  // 其实只需要考虑一侧即可，因为两侧互不影响，一侧的结果的平方就是答案
  const MOD = BigInt(1e9 + 7)
  let dp_0 = 1n, dp_1 = 2n; // dp[0] = 1, dp[1] = 2

  for (let i = 2; i <= n; i++) {
    const tmp = (dp_0 + dp_1) % MOD
    dp_0 = dp_1
    dp_1 = tmp
  }

  return Number((dp_1 * dp_1) % MOD)
};